/*
题目链接 : https://leetcode.cn/problems/substring-with-largest-variance/description/?envType=daily-question&envId=2025-03-16
*/

//题解代码:

/*
1.设答案的子串中, 次数最多的字符是c1, 次数最少的字符是c2
  枚举这两个字符, 且c1!=c2 (c1==c2时,ans=0)

2.把c1 映射为 1
  把c2 映射为 -1
  其余的映射为 0
题目就变成了求子数组的最大累加和, 注意子数组一定要包含至少一个c1 和 至少一个c2

3.根据以上,字符串被映射成了一个等长的-1,0,1数组,
定义  : f[i][0] : 以第i个元素结尾的子数组最大累加和
      : f[i][1] : 以第i个元素结尾的子数组,必须包含-1(c2)的最大累加和

转移 : f[i][0] = max(f[i-1],0) + cur;
       cur==-1 : f[i][1] = f[i-1][0] + cur;
       other   : f[i][1] = f[i-1][1] + cur;  
*/
class Solution {
public:
    int largestVariance(string s) {
        int n = s.size(),ans = 0;
        vector<vector<int>> f(n+1,vector<int>(2,0));
        f[0][1] = INT_MIN;
        for(char c1='a';c1<='z';++c1){
            for(char c2='a';c2<='z';++c2){
                if(c1 == c2) continue;
                for(int i=1;i<=n;++i){
                    f[i][0] = 0;
                    f[i][1] = INT_MIN;//初始化
                    int cur = 0;
                    if(s[i-1]==c1) cur=1;
                    else if(s[i-1]==c2) cur=-1;
                    f[i][0] = max(f[i-1][0],0) + cur;
                    if(cur==-1){
                        f[i][1] = max(f[i-1][0],0) + cur;
                    }else{
                        f[i][1] = f[i-1][1] + cur;
                    }
                    ans = max(ans,f[i][1]);
                }
            }
        }
        return ans;
    }
};
